2018-04-08

AP CS复习（1）- String类及其API

很久之前就有开一个博客写文章的打算然而迟迟未能动笔。最近正好发现没有什么专门复习AP CS的文章，所以就准备自己写一个。仔细想想，很多人会觉得AP CS很水很弱智，所以我希望我写出的东西能够不只是应付AP本身，还要能够挖掘相对底层一点的东西（如某些方法的实现）。
第一篇文章就从 Java.lang.String 这个概念讲起，大致概括AP的一些考点和一些额外的概念。

I: AP考什么?

先上一张图（来自CB Course Description）

CB对于String类的要求

可以看出，AP CS考试中对于String类的要求非常之低，除了通用的懂得如何实例化一个字符串之外，仅需要掌握5（其实是4）种方法就可以舒服的当一个api-caller了。
然而，除了懂怎么用之外，什么时候用则成为了一个更重要的问题。所以我们还是一个个方法逐一了解一下。

int length()

不用多说，这个最简单的方法返回该字符串的长度。而这个方法常用于for循环中来遍历字符串中的字符。

举例：

//打印出字符串"banana"中'a'字符的个数
String str = "banana";
int count = 0;
for (int i = 0; i < str.length(); i++) {
    if (str.charAt(i) == 'a') {
        count++;
    }
}
//输出为3
System.out.println(count);

当然，这里可耻的使用了一个 String.charAt(int index) 的方法，但是不影响理解就好了。关于 length() 能讲的实在不多，毕竟它太基础了。

稍微深入一点的话，不难发现String这个类其实是由一个char[]构成的。也就是说，一个”pig”这样的字符串本质上由’p’,’i’,’g’拼接而成。了解这一点，就不难发现String类有这样一个构造方法：

char[] arr = {'d','o','g'};
//传入一个char[]作为参数
String str = new String(arr);
//输出"dog"
System.out.println(str);

那么可想而知，length() 的底层实现也非常简单，就是返回char[]的length就可以了:

//String类中的实现
public int length() {
    return value.length;
}

###substring(int from, int to)###
下一个方法就是大名鼎鼎的 substring 方法。这个方法返回字符串中的一个子字符串，其上界和下界由参数中的from和to控制。为什么说这个方法很牛逼呢，其实是因为各种你想得到的方法都可以由 substring 方法得到。
但在这之前，有两点需要注意！

对于给定的参数from和to，返回的子字符串是从 charAt(from) 开始到 charAt(to-1) 为止。换句话说，返回的子字符串的长度应该等于to - from,这样记就不会弄错啦！

String test = "watermelon";
//0对应test中的'w'字符，而4却对应的是index为（4-1=3）的'e'字符。
//输出结果为"wate"
System.out.println(test.substring(0, 4));

可想而知，这个方法常常用于截取字符串上，许多的AP FRQ问题都会考到。
但是，这里substring方法的用处可不止如此，我们可以通过操纵参数达到意想不到的效果。

I：获取字符串的最后一个字符

String test = "hello";
//结果为o
String lastChar = test.substring(test.length()-1, test.length());
//上面也可以简写成（运用后面会讲的substring(int from)）
//String lastChar = test.substring(test.length()-1);

II: 究极脑经急转弯：如何不用遍历判断一个字符串是否由单一字符组成？

直接上代码，这个能不能理解都无所谓，只是真的让人感叹substring的强大。

public static boolean consistOfSameChar(String str) {
    //假设传入的str为"banana"
    //first = "banan" （除了最后一个字符）
    String first = str.substring(0, str.length-1);
    //last = "anana" （除了第一个字符）
    String last = str.substring(1, str.length());
    //判断他们是否相等即可判断该字符串是否由同一字符组成
    return first.equals(last);
}

最后，简单提一下 substring(int from) 这个方法，作为前一个方法的重写，这个方法更加的方便，直接返回从给定的index from到字符串末尾的子字符串。本质上:

1	x.substring(int from) 和 x.substring(int from, x.length()) 相同

int indexOf()

又是一个强大的方法！！
本质上idnexOf方法在String类中被复写了4遍。但操蛋又温柔的CB爸爸只要求考其中的一种，即参数为String的那种。

Talk is cheap, show me the code – Linus

我们废话少说，直接上一个清晰易懂的实例：

//被匹配的字符串
String test = "listar2000";
//想要查找的值
String match1 = "star";
//得出位置1
int position1 = test.indexOf(match1);
//输出结果为2，也就是说，首先listar2000中包含star这个子字符串，同时star中的第一个字符s在listar2000中的位置为2，所以返回一个int值=2。
System.out.println(position);
//下面我们再看另一种情况
String match2 = "michael";
//欸，明明listar2000里面不包含michael啊，怎么办呢?
int position2 = test.indexOf(match2);
//int值在字符串中不包含的情况下返回-1
System.out.println(position2);

言简意赅，雷厉风行。如果有，返回子字符串的起始位置；如果没有，返回-1。清晰明了。这样也可以看出，indexOf这个方法可以用来做匹配，查询字符串中是否包含某个段落。下面是最近CS Project里面的一段真实代码。

//判断字符串中是否含有某个子字符串
public static boolean hasSubstring(String str, String match) {
    if (str.indexOf(match)>=0) return true;
    return false;
}

当然，其实String类的API中早就已经预设好类似 contains 这样的方法直接返回一个boolean告诉你字符串是否包含。但是灵活掌握一种方法同时融会贯通的能力也是非常重要的。另一方面，这里也想着重强调官方文档的重要性，多看文档，会发现很多方法早就预设在jdk里面，不需要像我刚刚一样重复造轮子，非常麻烦! 传送门

int compareTo()

最后一个方法稍微有点复杂，所以我们从其源码的implementation角度来理解这个方法的具体功能。

public int compareTo(String anotherString) {
    //得到自身和同自身比较的字符串的长度
    int len1 = value.length;
    int len2 = anotherString.value.length;
    //得到两字符串较短的长度的值，如一个长为5，一个为3，则取3。
    int lim = Math.min(len1, len2);
    //得到两字符串分别的char[]，刚刚提过这是内置在String类中的成员变量
    char v1[] = value;
    char v2[] = anotherString.value;
    //下面开始注意!!
    //从两个字符串的第一个字符开始遍历，到刚刚得到的最短长度为止
    //将每一个index的字符进行比较，如果不相同则返回c1 - c2的差
    //注意，java中char类型的差为ASC-II码表上对应的值。比如A的值为65，a     的值却是97，那么'a'-'A'就等于32.
    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    //如果在0到lim范围内两字符串的字符都相同，那么返回的int值不再是ASC-II码表编号的差距，而是直接两字符串长度的差！！
    return len1 - len2;
}

会发现十分操蛋的一点是，compareTo返回的int值，根据比较的两个字符串的不同，返回时的判定方式也不一样。要着重记住的点就是，java中char类型比较的是其ASC-II码表的编号差！！

算了，看完了底层实现，我们看一下实例来说明问题吧！

例子1：

String a = "applegood";
String b = "Apple";
System.out.println(a.compareTo(b));
//输出为32

执行compareTo方法
从第一个字符开始遍历，找不同。
发现第一个字符’a’和’A’就不一样
根据ASC-II码表，分别找出a（97）和A（65）的编号。
返回97-65=32.

例子2：
这次只改变了一个字符的大小写，结果截然不同啊！

String a = "applegood";
String b = "apple";
System.out.println(a.compareTo(b));
//输出为4

执行compareTo方法
从第一个字符开始遍历，找不同。
发现找到apple的末尾，也就是index=4还是一样！
不干了，直接返回两个字符串长度差，也就是4

这到底是什么JB玩意？!
Java就这样implement的？？？

PHP is the best programming language in the world!!
Life is short, I use Python!!

好吧说了这么多，反正AP也不会考这么深。但是着再一次的证明了阅读源码的重要性啊！！！不然鬼知道这个int返回值是什么东西。只要记住当 compareTo 返回的是0时，那么这两个字符串就是相等了。不过话说用equals不是更好么。。。

Beyond AP：来看看String类的魔性设定

首先我们看一下String这个类中源码的定义：

1 2	public final class String implements java.io.Serializable, Comparable<String>, CharSequence {}

抛开implements的那一大串接口不谈，你会发现一个恐怖的字眼 final class
更恐怖的是，作为String根本的成员变量char[]（之前提过），也是final修饰的。这也意味着，String这个对象本身其实是不可改变的。

有人马上会说，胡说八道！字符串的拼接是怎么实现的？
例如：

1 2	String test = "star"; test = test + "is handsome";

这不是改变了吗？
但其实，在我们每一次的进行字符串拼接的时候，其实Java底层都是创建了一个新的String对象来承载新的字符串。不信，可以用hashcode()方法测验一下(一般我们认为hashcode相同的两个object指向内存中的同一对象)。

String test = "star";
//3540562
System.out.println(test.hashCode());
test = test + "is handsome";
//-632481145
System.out.println(test.hashCode());

很明显的，对象改变了。事实上，针对String的hashcode有一个特殊的算法，保证内容相同的字符串拥有相同的hashcode。我们使用拼接改变字符串，自然让hashcode同样有了变化。
这就带来了一个问题!!
当我们的程序需要频繁的拼接字符串的时候，性能会由于频繁的new对象受到影响。而在Java这一成熟的语言中，要解决这个问题也是非常简单的。既然String是一个不可变的类，那么就用辅助的可变类来帮助进行频繁的拼接操作。如：StringBuffer和StringBuilder。

下面直接上一篇其他人博客的实验结果：

用String+=拼接字符串的时间27468
用String=String+拼接字符串的时间25813
用String.concat拼接字符串的时间12265
用StringBuffer.append拼接字符串的时间14
用StringBuilder.append拼接字符串的时间8

效果立杆见影，可想而知了吧。。。
具体的使用方法这里不多谈，希望大家可以查阅官方文档来获取资讯。

最后

第一篇博文是有点试试水的心态写的，如有疏漏请多原谅。本文借鉴了少数他人博客和大量官方文档，但最多的还是自己开着IDE进行测试。这里也鼓励各位多多肝码，自己尝试。
AP不到一个月了，作为Senior我觉得有时间可以写一下这方面的博客来帮助大家复习。同时，自己的Hexo博客刚开所以没有怎么设置，目前应该是没有留言功能的。所以大家想了解AP CS中的哪方面知识可以微信找我。就这样了！！

listar2000's Blog

Life/Java/Econ